//
//  binarySearchTreeMap.swift
//  SetAndMap
//
//  Created by lhc on 2024/7/21.
//

import Foundation


class BinarySearchTreeMap<K: Comparable, V: Comparable>: MyMap {
    
    class Node: Equatable {
        static func == (lhs: BinarySearchTreeMap<K, V>.Node, rhs: BinarySearchTreeMap<K, V>.Node) -> Bool {
            return lhs.key == rhs.key
        }
        
        var key: K
        var value: V
        var left: Node?
        var right: Node?
        init(key: K, value: V, left: Node? = nil, right: Node? = nil) {
            self.key = key
            self.value = value
            self.left = left
            self.right = right
        }
        
        
    }
    
    private var root: Node?
    private var size = 0
    
    func getSize() -> Int {
        return self.size
    }
    
    func isEmpty() -> Bool {
        return self.size == 0
    }
    
    /// 根据key找到对应的node
    private func getNodeByKey(_ key: K, from node: Node?) -> Node? {
        guard let node = node else {
            // 如果node为空了,说明不存在此key
            return nil
        }
        
        if key < node.key {
            return self.getNodeByKey(key, from: node.left)
        }else if key > node.key {
            return self.getNodeByKey(key, from: node.right)
        }else {
            // k == node.key
            return node
        }
    }
    
    /// 根据key查找value
    func getValueBy(key: K) -> V? {
        return self.getNodeByKey(key, from: self.root)?.value
    }
    
    /// 查看是否有对应的key的node
    func contains(key: K) -> Bool {
        if let node = self.getNodeByKey(key, from: self.root) {
            return true
        }else {
            return false
        }
    }
    
    
    /// 设置K-V(外部调用)
    func setValueBy(key: K, value: V) {
        self.root = self.setValueBy(key: key, value: value, node: self.root)
    }
    
    /// 设置K-V 内部递归调用
    private func setValueBy(key: K, value: V, node: Node?) -> Node {
        guard let node = node else {
            // 如果node为空说明应该在此添加结点
            self.size += 1
            return Node(key: key, value: value)
        }
        
        if key < node.key {
            node.left = self.setValueBy(key: key, value: value, node: node.left)
        }else if key > node.key {
            node.right = self.setValueBy(key: key, value: value, node: node.right)
        }else {
            // key == node.key
            // 设置新的value
            node.value = value
        }
        return node
    }
    
    /// 返回当前结点的最小值子结点
    private func minimumNodeFrom(node: Node) -> Node {
        guard let left = node.left else {
            // 如果当前结点的左子树为空那么当前结点就是最小值结点
            return node
        }
        return self.minimumNodeFrom(node: left)
    }
    
    /// 删除从当前node的最小值node并返回删除后新的搜索树的根
    private func removeMinimumNodeFrom(node: Node) -> Node? {
        if node.left == nil {
            let right = node.right
            node.right = nil
            self.size -= 1
            return right
        }
        
        node.left = self.removeMinimumNodeFrom(node: node.left!)
        return node
    }
    
    /// 删除元素(外部调用)
    func remove(key: K) -> V? {
        if let node = self.getNodeByKey(key, from: self.root) {
            self.root = self.remove(key: key, from: self.root)
            return node.value
        }else {
            return nil
        }
        
    }
        
    /// 删除元素(递归调用)
    private func remove(key: K, from node: Node?) -> Node? {
        guard let node = node else {
            return nil
        }
        
        if key < node.key {
            node.left = self.remove(key: key, from: node.left)
            return node
        }else if key > node.key {
            node.right = self.remove(key: key, from: node.right)
            return node
        }
        // 现在node.key == key
        
        if node.left == nil {
            let right = node.right
            node.right = nil
            self.size -= 1
            return right
        }
        
        if node.right == nil {
            let left = node.left
            node.left = nil
            self.size -= 1
            return left
        }
        
        // node.left node.right都不为空的情况
        
        // successor为比当前node的大的最小node
        let successor = self.minimumNodeFrom(node: node.right!)
        
        // 当前node右结点删除successor后作为successor的右结点
        successor.right = self.removeMinimumNodeFrom(node: node.right!)
        // 当前结点的左结点作为successor的左结点
        successor.left = node.left
        
        // 断开node的left right指针
        node.left = nil
        node.right = nil
        // 返回successor
        return successor
    }
    
    /// 层序遍历
    func leverOrder(action: (K) -> ()) {
        guard let root = self.root else {return}
        
        let queue = LinkListQueue<Node>()
        queue.enqueue(e: root)
        
        while !queue.isEmpty() {
            if let node = queue.dequeue() {
                
                // 获得key,然后执行外部赋予的方法
                action(node.key)
                
                if let left = node.left {
                    queue.enqueue(e: left)
                }
                if let right = node.right {
                    queue.enqueue(e: right)
                }
            }
        }
    }
}

extension BinarySearchTreeMap: CustomStringConvertible {
    var description: String {
        
        
        var elementArray = [K]()
        self.leverOrder { key in
            elementArray.append(key)
        }
        
        return "\(elementArray)"
        
    }
    
    
}
